package Datastruct.Algorithm.sort;

import java.util.Arrays;

/**
 * 快排--快速排序是对冒泡排序的一种改进。
 * 通过一趟排序将要排序的数据分割成独立的两部分，
 * 其中一部分的所有数据都比另一部分所有的数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，
 * 以此达到整个数据变成有序序列
 */
public class FastSort {

    public static void main(String[] args) {

        int []arrys={2,9,4,7,3,1,6,5};

        sort(arrys,0, arrys.length-1);
        System.out.println(Arrays.toString(arrys));
    }

    public  static   void  sort(int [] arr,int left,int right){
        int l=left;
        int r=right;

        //中间值
        int   midcount=arr[(left+right)/2];

        while (l<r){

            while (arr[l]<midcount){
                l++;
            }
            while (arr[r]>midcount){
                r--;
            }

            /**
             * l>=r 说明左边全是小于中间值的  右边全是大于中间值的
             */
            if(l>=r){
                break;
            }
            /**
             * 交换
             */
            arr[l]=arr[l]^arr[r];
            arr[r]=arr[l]^arr[r];
            arr[l]=arr[r]^arr[l];

            /**
             * 交换后发现 arr[l]==midcount 则 r--
             */
            if(arr[l]==midcount){
                r--;
            }
            /**
             * 交换后发现arrays[r] == midcount值，则l++；
             */
            if(arr[r]==midcount){
                l++;
            }

            /**
             * 如果 l==r  必须 r--  l++  否者堆栈溢出
             */
            if(l==r){
                l++;
                r--;
            }

            if(left<r){
                sort(arr,left,r);
            }
            if(right>l){
                sort(arr,l,right);
            }

        }
    }
}
